package 算法.NiuKe.JZ;

/**
 * @author:谢君臣
 * @Date:2021/3/2510:05
 * @version:1.0
 * @function: 输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。
 * 求所有子数组的和的最大值。要求时间复杂度为 O(n).
 */
public class JZ30 {
    public static void main(String[] args) {
        FindGreatestSumOfSubArray(new int[]{1, -2, 3, 10, -4, 7, 2, -5});
    }

    public static int FindGreatestSumOfSubArray(int[] array) {
        if (array.length < 1)
            return 0;
        int [] a = new int[array.length];
        a[0] = array[0];
        int max = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i-1]>0)
                a[i] = a[i-1]+array[i];
            else
                a[i] = array[i];
            max = Math.max(max,a[i]);
        }
        return max;
    }
}